\newpage

\subsection{Enhancing Join Processing Efficiency}
\noindent
(Brute-force is bad. Index should be used.)

One simple way of processing the streaming join is by brute-force pairwise comparison upon first-in-first-out (FIFO) queues~\cite{sigmod11:Teubner}. However, it is far from efficient unless most of the tuple pairs satisfy the join predicate, which is rare in practice. In order to improve the performance, ESJ uses in-memory index to accelerate the join processing. When a tuple joins with the opposite stream, it searches for the join keys satisfying the predicate via index, and then join with the tuples associated with the join keys found. The performance gain comes from the avoidance of unnecessary comparison. 

\noindent
(Why use BST and hash.)

ESJ supports both inequality join and equality join. Since the inequality operator requires accessing range of join keys indicated by the predicate, the balanced binary search tree (BST) index is suitable for the processing of inequality join. On the other hand, since the equality operator only requires single join key accessing, hash index is preferable for the processing of equality join. The keys maintained in BST and hash indices are the join keys of the corresponding predicate. 

\noindent
(End)

Our experiment shows that the benefit of the index assised streaming join processing could be orders of magnitude when the streaming input is large. A corresponding quantitative analysis is given in Appendix~\ref{append:join}.
